package com.mzy.linear_struct.hot100.二叉树;

import java.util.Arrays;

/**
 * @Author: mizy3
 * @Date: 2024/08/20/上午2:10
 * @Description:
 */
public class Pro105从前序与中序遍历序列构造二叉树 {

    public TreeNode buildTree(int[] preorder, int[] inorder) {

        return build(preorder, 0, preorder.length, inorder, 0, inorder.length);
    }

    private TreeNode build(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        if (preStart >= preEnd || inStart >= inEnd) return null;

        if (preorder.length == 1) return new TreeNode(preorder[0]);
        System.out.println(preStart);
        int rootValue = preorder[preStart];

        TreeNode tree = new TreeNode(rootValue);

        // 获取中序遍历数组中根节点的下标
        int rootIndex = 0;
        while (rootValue != inorder[rootIndex]) {
            rootIndex++;
        }

        int leftNum = rootIndex - inStart;
        tree.left = build(preorder, preStart + 1, preStart + leftNum + 1, inorder, inStart, rootIndex);
        tree.right = build(preorder, preStart + leftNum + 1, preEnd, inorder, rootIndex + 1, inEnd);
        return tree;
    }

    public static void main(String[] args) {
        new Pro105从前序与中序遍历序列构造二叉树().buildTree(new int[]{3, 9, 20, 15, 7}, new int[]{9, 3, 15, 20, 7});
        // new Pro105从前序与中序遍历序列构造二叉树().buildTree(new int[]{1, 2}, new int[]{1, 2});
    }
}